package oj_leetcode;

public class LongestValidParentheses {
    public int longestValidParentheses(String s) {
        if (s.length() <= 1) {
            return 0;
        }
        // 顺序的找弹栈出现问题的串，记录该串的最大匹配
        int index = 0;
        int maxMatch = 0;
        while (index < s.length()) {
            int leftCount = 0; // 栈剩余量
            int matchCount = 0; // 当leftCount为0时，可以记录当前闭合term的匹配数量
            int allmatchCount = 0; // 所有闭合term的匹配数量之和
            int notClosedMatchCount = 0;// 没有闭合的term的最大匹配数量

            int[] mapCount = new int[s.length() + 1]; // 当前term，不同【未匹配数量left count】作为【起始】的已匹配数量
            while (leftCount >= 0 && index < s.length()) {
                if (s.charAt(index) == '(') {
                    leftCount++;
                } else {
                    if (leftCount > 0) {
                        mapCount[leftCount] = mapCount[leftCount] + 1;// 记录当前term，不同【未匹配数量left count】作为【起始】的已匹配数量
                        if (mapCount[leftCount + 1] != 0) { // 合并【高的起始】的已匹配数量，由于 leftCount 走到这里必然 < s.length，所以不必检查下标
                            mapCount[leftCount] += mapCount[leftCount + 1];
                            mapCount[leftCount + 1] = 0;
                        }
                        matchCount++;
                        leftCount--;
                    } else {
                        leftCount--;
                    }
                    if (leftCount == 0) {
                        // term闭合，累加，重置
                        allmatchCount += matchCount;
                        matchCount = 0;
                        mapCount = new int[s.length()];
                    }
                }
                index++;
            }

            // 未闭合term，不同起始偏移，最大的匹配数量
            for (int i = 0; i < s.length(); i++) {
                if (mapCount[i] > notClosedMatchCount) {
                    notClosedMatchCount = mapCount[i];
                }
            }
            // 和闭合的做比较
            int matchCandidate = Math.max(notClosedMatchCount, allmatchCount);
            if (maxMatch < matchCandidate) {
                maxMatch = matchCandidate;
            }
        }
        return maxMatch * 2;
    }

    public static void main(String[] args) {
        new LongestValidParentheses().longestValidParentheses("(((()(()");
    }
}
